package com.cty.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Graph {
    private List<String> list;
    private int[][] Edges;
    private int numOfEdges;
    private boolean[] isVisited;

    //初始化图
    public Graph(int n) {
        Edges = new int[n][n];
        list = new ArrayList<>(n);
        isVisited = new boolean[n];
        numOfEdges = 0;
    }

    //寻找第一个临接结点
    public int findFirstNeighbor(int i) {
        for (int j = 0;j < list.size();j++) {
            if (Edges[i][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    //寻找下一个临接结点的下一个结点
    public int findNextNeighbor(int v1,int v2) {
        for (int j = v2 + 1; j < list.size();j++) {
            if (Edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    //深度优先遍历
    private void dfs(boolean[] isVisited,int i) {
        System.out.print(getValueByIndex(i) + "->");
        isVisited[i] = true;
        int w  = findFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                dfs(isVisited,w);
            }
            w = findNextNeighbor(i,w);
        }
    }

    //广度优先遍历
    private void bfs(boolean[] isVisited,int i) {
        int u;
        int w;
        System.out.print(getValueByIndex(i) + "=>");
        LinkedList<Object> queue = new LinkedList<>();
        isVisited[i] = true;
        queue.addLast(i);
        while (!queue.isEmpty()) {
            u = (Integer) queue.removeFirst();
            w = findFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = findNextNeighbor(u,w);
            }
        }

    }

    public void bfs() {
        for (int i = 0;i < numOfVertex();i++) {
            if (! isVisited[i]) {
                bfs(isVisited,i);
            }
        }

    }

    public void dfs() {
        for (int i = 0;i < numOfVertex();i++) {
            if (!isVisited[i]) {
                dfs(isVisited,i);
            }
        }
    }

    //插入顶点
    public void insertVertex(String vertex) {
        list.add(vertex);
    }

    //插入路径
    public void insertEdge(int v1,int v2,int weight) {
        Edges[v1][v2] = weight;
        Edges[v2][v1] = weight;
        numOfEdges++;
    }

    //返回邻接矩阵
    public void showEdges() {
        for (int[] edges: Edges) {
            System.out.println(Arrays.toString(edges));
        }
    }

    //返回图的顶点数
    public int numOfVertex() {
        return list.size();
    }

    //返回图的路径数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //返回对应下表的值
    public String getValueByIndex(int index) {
        return list.get(index);
    }

    //返回v1和v2对应的权值
    public int getWeight(int v1,int v2) {
        return Edges[v1][v2];
    }
}
